The present invention relates to route planning in a metropolitan area. A goal of route planning is to determine how to travel from one location to other location using the vehicles available from various providers of transport services. Often it is required for the travel to last as little time as possible, or depart at a certain time, among other requirements. A route typically specifies instructions for a rider, including walk paths and vehicle ride paths.